package tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Tree {
    public static void main(String[] args) {
        TreeNode<Integer> root = new TreeNode<Integer>(8,
                new TreeNode<Integer>(6,
                        new TreeNode<Integer>(3,
                                new TreeNode<Integer>(1), new TreeNode<Integer>(2)),
                        new TreeNode<Integer>(7)),
                new TreeNode<Integer>(9));
        root.print();
        System.out.println("====================");
        System.out.println("Maximum depth: " + TreeNode.getMaxDepth(root));
    }


    private static class TreeNode<T> {
        private final TreeNode<T> left;
        private final TreeNode<T> right;
        private final T value;

        private TreeNode(T value) {
            this.left = null;
            this.right = null;
            this.value = value;
        }

        private TreeNode(T value, TreeNode<T> left, TreeNode<T> right) {
            this.left = left;
            this.right = right;
            this.value = value;
        }

        public static <T> int getMaxDepth(TreeNode<T> node) {
            if (node == null) {
                return 0;
            }
            return Math.max(getMaxDepth(node.left), getMaxDepth(node.right)) + 1;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "left=" + left +
                    ", next=" + right +
                    ", value=" + value +
                    '}';
        }

        public void print() {
            Queue<TreeNode<T>> currentLevelNodes = new LinkedList<TreeNode<T>>();
            Queue<TreeNode<T>> nextLevelNodes;
            currentLevelNodes.add(this);
            int levelNumber = 0;

            int numberOfLevels = getMaxDepth(this);
            do {
                nextLevelNodes = new LinkedList<TreeNode<T>>();
                int levelOffset = 0;
                while (!currentLevelNodes.isEmpty()) {
                    int numberOfSpacesBefore = 2*(numberOfLevels - levelNumber-1) -  levelOffset;
                    TreeNode<T> current = currentLevelNodes.poll();
                    char[] spaceChars = new char[numberOfSpacesBefore];
                    Arrays.fill(spaceChars,' ');
                    String spacesPrefix = new String(spaceChars);
                    System.out.print(spacesPrefix+current.value + " ");
                    if (current.left != null) {
                        nextLevelNodes.add(current.left);
                    }
                    if (current.right != null) {
                        nextLevelNodes.add(current.right);
                    }
                    levelOffset++;
                }
                levelNumber++;
                currentLevelNodes = nextLevelNodes;
                System.out.println();
            } while (!nextLevelNodes.isEmpty());
        }
    }
}